package com.wx.leetcode;

/**
 * @ClassName SearchMatrixTopic
 * @Author wx
 * @Description 编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
 * 每行中的整数从左到右按升序排列。
 * 每行的第一个整数大于前一行的最后一个整数。
 * 示例 1:
 * 输入:
 * matrix = [
 * [1,   3,  5,  7],
 * [10, 11, 16, 20],
 * [23, 30, 34, 50]
 * ]
 * target = 3
 * 输出: true
 * 示例 2:
 * <p>
 * 输入:
 * matrix = [
 * [1,   3,  5,  7],
 * [10, 11, 16, 20],
 * [23, 30, 34, 50]
 * ]
 * target = 13
 * 输出: false
 * @Date 2020-04-11-23:29
 */
public class SearchMatrixTopic {

    public static boolean searchMatrix(int[][] matrix, int target) {

        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int length = matrix[0].length;
        //获取总长度
        int n = matrix.length * length;
        return binary(matrix, 0, n - 1, length, target);

    }

    //二分
    public static boolean binary(int[][] matrix, int startIndex, int endIndex, int length, int target) {
        if (startIndex > endIndex) {
            return false;
        }
        //计算中间值
        int middle = startIndex + ((endIndex - startIndex) / 2);

        //抽象成一个数组，计算下标
        int pivotElement = matrix[middle / length][middle % length];
        if (target == pivotElement) {
            return true;
        } else if (target < pivotElement) {
            endIndex = middle - 1;
        } else {
            startIndex = middle + 1;
        }
        return binary(matrix, startIndex, endIndex, length, target);
    }

    public static void main(String[] agrs) {
        int[][] matrix = new int[][]{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 50}};
        System.out.println(searchMatrix(matrix, 3));
    }
}
